package B刷题.暴力递归.A回溯;

import java.util.ArrayList;
import java.util.List;

/**
 * @author wei.zhao
 * @description: 剑指 Offer II 085.生成匹配的括号
 * @date 2022年04月11日 13:36
 */
public class Code06_GenerateParenthesis {

    public List<String> result = new ArrayList<>();

    public List<String> generateParenthesis(int n) {
        if (n == 0) {
            return result;
        }
        process("", 0, 0, n);
        return result;
    }

    private void process(String s, int left, int right, int n) {
        if (left + right == 2 * n) {
            result.add(s);
            return;
        }
        if (left < n && right < left) {
            // 左右括号都可以添加
            process(s + "(", left + 1, right, n);
            process(s + ")", left, right + 1, n);
        } else if (right == left) {
            // 只能添加左括号
            process(s + "(", left + 1, right, n);
        } else {
            // 只能添加右括号
            process(s + ")", left, right + 1, n);
        }
    }

}
